§1.1 Field of the Invention
The present invention concerns sensor fingerprint based source device identification.
§1.2 Background Information
Promising research results have emerged in recent years in identifying the source acquisition device (e.g., camera, video camera, camera enabled smart phone, etc.) of multimedia objects. These efforts have primarily focused on the design of techniques that can identify and extract class properties (the type of color filter array, specifics of the demosaicing technique, type of lens, compression parameters) and individual properties (noise characteristics of the imaging sensor and traces of sensor dust of images and videos). (See, e.g., the articles: J. Lukas, J. Fridrich, and M. Goljan, “Digital Camera Identification From Sensor Pattern Noise,” IEEE Transactions Information Forensics and Security 1(2), pp. 205-214, (2006); S. Bayram, H. T. Sencar, and N. Memon, “Classification Of Digital Camera Models Based On Demosaicing Artifacts,” Digital Investigation: The International Journal of Digital Formesics & Incident Response, 5, pp. 49-59, (September 2008); K. S. Choi, E. Y. Lam, and K. K. Y. Wong, “Source Camera Identification Using Footprints From Lens Aberration,” Digital Photography II. Proceedings of the SPIE 6069, pp. 172-179, (February 2006); A. Swaminathan, M. Wu, and K. J. R. Liu, “Non Intrusive Forensic Analysis Of Visual Sensors Using Output Images,” IEEE Transactions of Information Forensics and Security 2, pp. 91-106, (March 20070), A. E. Dirik, H. T. Sencar, and N. Memon, “Digital Single Lens Reflex Camera Identification From Traces Of Sensor Dust,” IEEE Transactions on TIFS, (2008); Z. J. Geradts, J. Bijhold, M. Kieft, K. Kurosawa, K. Kuroki, and N. Saitoh, “Methods For Identification Of Images Acquired With Digital Cameras,” SPIE, Enabling Technologies for Law Enforcement and Security 4232, pp. 505-512, (February 2001); K. Kurosawa, K. Kuroki, and N. Saitoh, “CCD Fingerprint Method Identification Of A Video Camera From Videotaped Images,” ICIP99, pp. 537-540, Kobe, Japan, (1999); H. T. Sencar and N. Memon, “Overview Of State-Of-The-Art In Digital Image Forensics”, World Scientific Press, (2008), each of which is incorporated herein by reference.) Methods to identify the unique fingerprint of a source device (e.g., digital camera) which is present in every image taken with the camera are described in Lukas, Fridrich and Goljan (2006), much like how every gun leaves unique scratch marks on every bullet that passes through its barrel. Furthermore, this unique fingerprint is hard to remove or forge and survives a multitude of operations performed on the image such as blurring, scaling, compression, and even printing and scanning. It can be detected with very high accuracy with false positives and negatives below 10−6.
Although the existence of multimedia forensics techniques is essential in determining the origin, veracity and nature of media data, with the explosive growth in the amount of media data, a more fundamental question also arises as how to integrate these methods into investigative and forensic settings in a more practical manner. For example, when triaging information from distributed sources, analysts may need to verify whether there are additional copies of a received picture or video that might have been captured by the same camera or camcorder, or may need to find the owner of an anonymized multimedia object containing contraband content. More critically, the analysts may need to find such instances from local databases or open sources, like the Internet for example, very fast.
Consider the following very specific scenarios:                1) The XY Times, the leading newspaper of XY city, receives a set of pictures from a terrorist organization claiming responsibility of a bombing event. The pictures show the scene just before the bomb was triggered thereby establishing complicity of the organization in the crime. A few days later, based on an anonymous tip, law enforcement agents raid a suspected hideout. A detailed forensics search of the computer found in the hideout uncovers no evidence linking the suspects to the crime. However, they find a camera on location whose “fingerprint” obtained by forensics analysis matches the picture sent to XY Times thereby clearly establishing the link between the suspects and the crime;        2) As above, The XY times again gets the same set of pictures for the same event. However, there is no anonymous tip this time. Instead, law enforcement agents now extract an estimate of the camera “fingerprint” from the pictures received by XY Times. They then perform a search for images on the internet, including online photo repositories, which have the same “fingerprint”. The search results in the discovery of a few hundred images that were potentially taken from the same camera as the pictures sent to XY Times. Manual inspection of this set leads to a group of pictures on a social media Website account apparently taken at a wedding celebration and depicting adults who fit a suspected profile. More detailed traditional investigation ultimately leads to the arrest of these adults and the breaking up of a major terrorist organization; and        3) A person is apprehended while suspiciously taking pictures of children near an elementary school. He claims to be an amateur photographer pursuing a hobby. The police extract a fingerprint of his camera and search a large database (of millions of images) of known child pornography images. A cluster of such recently reported images is found to match the suspect's camera fingerprint. The suspect is questioned, the child depicted in the pictures is rescued and the suspect is convicted after a short trial and put behind bars.        
It should be noted that the problem in the first example above is an instance of the multimedia source “verification” problem, i.e., one is trying to match a given object to a given device. On the other hand, in the second and third scenarios, the task turns into a multimedia source “identification” problem where one has to do a comparison with all the entities in a large database to decide which objects in the database match the query device or the query object.
One solution to the identification problem would be to use multiple one to one comparisons using conventional source verification techniques. However this would require comparisons linear to (on the order of) the size of the database as shown in FIG. 1. For large databases, this is not feasible. Specifically, conventional source identification techniques can be viewed to include an offline and online step. During the offline step, fingerprints from (1) all the available images and videos and (2) the available source devices are extracted and saved. Typically, the computational requirements of this step are quite intensive; however, since it is done only once per media object, it is surmountable pending on the specifics of the decision scenario. This might include as few as a hundred objects, to large databases of millions of objects. During the online step, a matching decision is sought for the provided media object(s). The computational requirements of the online step will vary depending on the specifics of the decision scenario. For example, when a match between an image and a camera is in question, the computational load may be negligible. On the other hand, when for a given camera fingerprint, all the copies of images taken by the same camera are to be searched over a large database, then the computational load may be determined by the size of the database.
The conventional linear matching methodology, for a given sensor fingerprint associated with a device, operates on each media object individually by correlating the device fingerprint with the fingerprint extracted from each media object. Therefore, computational complexity may be linear in the size of the database. Hence for large databases, no matter how simple the matching operation is, the computational burden will be in the order of the size of database. Since video and image databases today often contain a very large number of objects, identifying source of a media object in a reasonable time duration is desirable. In this paradigm, the online step of the sensor fingerprint matching method has been a bottleneck for real-life retrieval scenarios, and has limited the benefit of the previously developed techniques.
FIG. 1 illustrates a linear search to identify a matching object for a given sensor fingerprint. In FIG. 1, fA shows the device fingerprint and pi (i=1, 2 . . . , N) shows the fingerprints of the media objects in the database to be searched.
Although the overwhelming amount of multimedia information is one of the most significant challenges faced by source-device identification techniques, computational scalability has not been a major concern for current the techniques. As a result, even if the above conventional techniques perform quite reliably, their success will be quite limited in applications that involve large databases simply due to the sheer volume of the data and impractical due to computational limitations and time constraints. It would be useful to have techniques that will make source identification, such as in the multimedia forensic analysis described in examples two and three above, practical and effective.